import math


# 归并两个有序的数组
def merge(A, p, q, r):
    n1 = q-p+1
    n2 = r-q
    L = [0]*n1
    R = [0]*n2
    for i in range(n1):
        L[i] = A[p+i]
    for j in range(n2):
        R[j] = A[q+j+1]
    i = 0
    j = 0
    for k in range(p, r+1):
        # 当第一个数组遍历完，第二个数组还未遍历完时，将第二个数组后边的元素追加在A后面
        if i == n1:
            for t in range(n2-j):
                A[k+t] = R[j+t]
            break
        # 当第一个数未组遍历完，第二个数组遍历完时，将第一个数组后边的元素追加在A后面
        if j == n2:
            for t in range(n1-i):
                A[k+t] = L[i+t]
            break
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i+1
        else:
            A[k] = R[j]
            j = j+1


# 递归的调用归并排序
def merge_sort(A, p, r):
    if p < r:
        q = math.floor((p+r)/2)
        merge_sort(A, p, q)
        merge_sort(A, q+1, r)
        merge(A, p, q, r)


# A = [10, 9, 2, 4, 1, 2, 3, 6]
A = [5, 2, 4, 7, 1, 3, 2, 6]
merge_sort(A, 0, len(A)-1)
print(A)

